package problem22_Generate_Parentheses;

import java.util.LinkedList;
import java.util.List;

public class Solution {
	 public List<String> generateParenthesis(int n) {
		 String str="";
		 List<String> list=new LinkedList<>();
		 generateParenthesis(n,0,0,list,str);
		 return list;
	 }
	 
	 private void generateParenthesis(int n,int i,int j,List<String> list,String str){
		 if(i==n&&j==n)
			 list.add(str);
		 if(i<n)
			 generateParenthesis(n,i+1,j,list,str+"(");
		 if(j<n&&j<i)
			 generateParenthesis(n,i,j+1,list,str+")");
	 }
}
